1. Field of the Invention
This invention relates to non-volatile content addressable memory.
2. Description of Related Art
A content addressable memory (CAM) can store a large amount of data for simultaneous comparisons with input values. The conventional CAM includes an array of CAM cells where each row of the CAM array corresponds to a stored word. The CAM cells in a row couple to a word line and a match line associated with the row. A word line connects to a control circuit that can select the row for a write operation or bias the word line for a search. The match line carries a signal that during a search, indicates whether the word stored in the row matches an input value. Each column of the conventional CAM array corresponds to the same bit position in all of the words, and the CAM cells in a column couple to a pair of bit lines associated with the column. A search applies to each pair of bit lines, a pair of complementary binary signals that represent a bit of an input value. Each CAM cell changes the voltage on the associated match line if the CAM cell stores a bit that does not match the bit represented on the attached bit lines. Accordingly, if the voltage on a match line remains unchanged during a search, the word stored in that row of CAM cells is equal to the input value.
Known CAM cells are based on SRAM, DRAM, or non-volatile memory circuits. SRAM-based and DRAM-based CAM cells are relatively fast but must be initialized by writing a complete set of data word to the CAM when the CAM is powered up or after a power failure. Non-volatile CAM avoids the overhead and delay required for initialization of the volatile CAM since the data values remain stored in non-volatile CAM cells even when power is off. Further, non-volatile CAM requires fewer transistors and less silicon area than do SRAM-based CAM cells. FIG. 1 shows a conventional non-volatile CAM cell 100 which includes two floating-gate transistors 111 and 112 coupled to a word/match line 120, a source line 130, and a pair of bit lines 141 and 142. Word/match line 120, which couples to the drains of transistors 111 and 112, acts as both the word line and the match line for CAM cell 100. Source line 130 grounds the sources of transistors 111 and 112, and bit lines 141 and 142 couple to respective control gates of transistors 111 and 112.
CAM cell 100 can store single bit of data and compare the stored bit to an input bit that signals on bit lines 141 and 142 represent. Before writing a bit in non-volatile CAM cell 100, floating-gate transistors 111 and 112 are erased. One erase operation applies a high voltage (e.g., 12 to 15 volts) to line 120 or 130 (i.e., to the drains or sources of transistors in a row of CAM cells) and grounds bit lines 141 and 142 (the control gates). This process causes Fowler-Nordheim tunneling that removes electrons from the floating gates of transistors 111 and 112 and lowers the threshold voltages of transistors 111 and 112. The erase operation places transistors 111 and 112 in a low threshold voltage state, for example, where the threshold voltage is less than the supply voltage Vcc for the CAM. For example, a floating-gate transistor in the low threshold voltage state may have a threshold voltage Vt less than about 3 volts when supply voltage Vcc is 5 volts, less than about 1 volt when supply voltage Vcc is 3 volts, or less than about 0.5 volts when supply voltage Vcc is 1.8 volts.
Floating-gate transistors 111 and 112 are individually programmable. Programming raises the threshold voltage of a floating-gate transistor to a level higher than supply voltage Vcc. For example, a floating-gate transistor in the high threshold voltage state may have a threshold voltage Vt of greater than 6 volts in a CAM where a supply voltage Vcc is 5 volts, more than 4 volts if supply voltage Vcc is 3 volts, or more than 2.8 volts if supply voltage Vcc is 1.8 volts. In accordance with one storage convention, programming transistor 111 in the high threshold voltage state while transistor 112 remains in the low threshold voltage state stores a 1 in CAM cell 100, and programming transistor 112 to the high threshold voltage state while transistor 111 remains in the low threshold voltage state, writes a 0 in CAM cell 100. A program process for a selected floating-gate transistor 111 or 112 in the CAM array raises the bit line 141 or 142 coupled to the selected floating-gate transistor 111 or 112 to a high programming voltage Vpp (e.g., about 8 to 12 volts) and raises the word line 120 coupled to the selected CAM cell to an intermediate programming voltage Vw (e.g., 5 to 6 volts). Other unselected bit lines and word lines in the CAM array remain grounded or float. Source line 130 is grounded. The combination of these voltages on the selected floating-gate transistor 111 or 112 causes channel hot electron injection that programs the select transistor. Typically, a programming operation simultaneously programs multiple selected transistors 111 and/or 112 in multiple CAM cells 100 associated with the same CAM word or entry.
A search biases match lines 120 with a low-current, voltage source and applies complementary binary signals bit lines 141 and 142 to represent the bits of an input value. For the example storage convention described above, if a bit has value 1, an associated bit line 141 is at supply voltage Vcc, and an associated bit line 142 is grounded. If CAM cells 100 stores 1, transistor 111 has a high threshold voltage, and voltage Vcc on the control gate of transistor 111 does not turn on transistor 111. Similarly, grounding bit line 142 fails to turn on transistor 112 even when transistor 112 is in the low threshold voltage state. Since neither transistor 111 nor 112 conducts, CAM cell 100 does not pull down the voltage on the match line. If CAM cells 100 stores 0, transistor 111 has the low threshold voltage, and voltage Vcc on the control gate of transistor 111 causes transistor 111 to conduct and pull down the voltage on match line 120. A sense amplifier connected to match line 120 senses whether any CAM cells on match line 120 conduct and thereby determines whether the input value matches the stored word.
Table 1 indicates the possible combinations of stored and input bits and parameters of CAM cell 100 during a search.
TABLE 1 Possible Search Combinations Stored Bit/ Vt for Vt for BL 141 BL 142 ML Input Bit 111 112 Voltage Voltage 120 Result 0/0 Low High Ground Vcc High Match 0/1 Low High Vcc Ground Low No Match 1/0 High Low Ground Vcc Low No Match 1/1 High Low Vcc Ground High Match X/0 High High Ground Vcc High Match X/1 High High Vcc Ground High Match
A match for a CAM word occurs when all of the CAM cells in the row corresponding to the word find a match so that none of the CAM cells discharges the voltage of the match line down.
Programming both transistors 111 and 112 in CAM cell 100 to the high threshold voltage state places the CAM cell in a "don't care" state designated herein by a stored value "X". In the don't-care state, CAM cell 100 indicates a match regardless of the input bit for a search. CAMs implementing a "don't care" state, for local bit-by-bit masking, are commonly referred to as ternary CAMs.
The conventional Flash CAM architecture using two-transistor CAM cells such as CAM cell 100 suffers from several drawbacks. One drawback is that a search operation must be delayed if immediately after a write operation because the CAM needs to erase a word before a programming operation or a search can begin. Even with 0.25 .mu.m Flash technology, erase and programming times are expected to be about 0.1 to 10 ms and 0.1 to 1 .mu.s, respectively. Therefore, the inability to write a data word and then immediately perform a search severely affects the overall performance of non-volatile CAM. Additionally, programming multiple CAM cells in parallel, which is necessary to improve write performance, results in large word line current which require huge column pass transistors. Another disadvantage is that programming CAM cells to the "don't care" state to mask individual bits that are not relevant to a particular search destroys the original data in the CAM. Methods and structures that improve performance of non-volatile CAM, permit local bit-by-bit masking of individual bits in a non-volatile CAM without destroying data, and facilitate parallel programming of a large number of cells on the same word line or entry are desirable.